/**
This module defines four structs for compile-time _reflection:
$(UL
  $(LI $(DECLREF Type) represents a type.)
  $(LI $(DECLREF Literal) represents a compile-time constant.)
  $(LI $(DECLREF Symbol) represents a fully-qualified symbol
       (identifier or template instance).)
  $(LI $(DECLREF TemplateArgument) represents a template instantiation
       argument.)
)
These structs are CTFE-friendly algebraic types. The $(D kind) field
indicates what is in a struct, and the other fields describe detailed
information. The use of those fields depends on the value of the
$(D kind) field.

Example:

The use of $(D Type.next[0]) differs between array and function types.
--------------------
Type ty = getSomeType();

switch (ty.kind)
{
    case Type.Kind.ARRAY:
        Type elementType = ty.next[0];
        break;

    case Type.Kind.FUNCTION:
        Type returnType = ty.next[0];
        break;

    // ...
}
--------------------

Restriction:

Functions $(D toString) and $(D equal) are defined for each struct.
These functions are free functions, not member functions, so that they
can be executed at compile time.
--------------------
template variable(alias type)
{
    mixin (toString(type) ~ " variable;");
}
// equivalent to const(int) variable;
mixin variable!(Type(Type.Kind.INT, StorageClass.CONST));
--------------------

BUGS:
A compiler bug $(BUGZILLA 3026) must be fixed.

Macros:
  DECLREF = $(LINK2 #$1, $(D $1))
 */
module nonstd.reflection;

import    std.stdint;
import nonstd.string;

private alias nonstd.string.toString toString;


//===================================================================//
// Utilities
//===================================================================//

/*
Construct a struct literal.
 */
version (unittest)
private template makeStruct(S, init...)
    if (is(S == struct))
{
    enum S makeStruct = makeStructImpl!(S, init);
}

// [internal]
private template makeStructImpl(S, init...)
{
    mixin (
    "S makeStructImpl()"
    "{"
        "S s;"
        ~ makeStruct_generateCode(init.length / 2) ~
        "return s;"
    "}"
    );
}

// [internal]
private string makeStruct_generateCode(size_t n) pure nothrow
{
    string stmt;

    foreach (uintmax_t i; 0 .. n)
    {
        string name = "init[" ~ toString(2*i    ) ~ "]";
        string expr = "init[" ~ toString(2*i + 1) ~ "]";
        stmt ~= `mixin("s." ~ ` ~ name ~ ` ~ " = ` ~ expr ~ `;");`;
    }
    return stmt;
}

unittest
{
    struct S { real r1, r2; }

    enum S s1 = makeStruct!(S);
    static assert(s1.r1 !<>= 0 && s1.r2 !<>= 0);

    enum S s2 = makeStruct!(S, "r2", 4.2);
    static assert(s2.r1 !<>= 0 && s2.r2 == 4.2);
}


//===================================================================//
// Type system
//===================================================================//

/***************************************
A bitwise-OR of $(D StorageClass) member values represents a storage
class.

Example:
--------------------
alias StorageClass STC;

STC stoc = STC.SHARED | STC.CONST | STC.LAZY;
assert(toString(stoc, "Type") == "lazy shared(const(Type))");
--------------------
 */
enum StorageClass : uint
{
    /**
     * No storage class. Note that the value of $(D NONE) is zero; it's
     * actually not a bit mask. Thus, given a storage class value
     * $(D x), to determine whether $(D x) does not have any storage
     * class, you may want to see if $(D x == NONE) rather than
     * $(D x & NONE).
     */
    NONE = 0,

    /**
     * Type-constructing storage classes. The only composite
     * type-constructing storage class that makes sense is
     * $(D _SHARED|CONST).
     */
    SHARED    = 1 << 0,
    CONST     = 1 << 1, /// ditto
    IMMUTABLE = 1 << 2, /// ditto

    /**
     * Parameter storage classes. $(D IN), $(D OUT), $(D REF) and
     * $(D LAZY) are exclusive each other. For example, $(D IN|REF)
     * does not make sense.
     */
    SCOPE = 1 << 3,
    IN    = 1 << 4, /// ditto
    OUT   = 1 << 5, /// ditto
    REF   = 1 << 6, /// ditto
    LAZY  = 1 << 7, /// ditto

    /**
     * A bit mask comprised of the type-constructing storage classes.
     */
    TYPECTOR = SHARED | CONST | IMMUTABLE,

    /**
     * A bit mask comprised of the parameter storage classes.
     */
    PARAMETER = SCOPE | IN | OUT | REF | LAZY,
}

/// Ditto
string toString(StorageClass stoc, string type) pure nothrow
{
    alias StorageClass STC;
    string s = type;

    // type storage class (in this order for "shared(const(T))")
    if (stoc & STC.CONST    ) s =     "const(" ~ s ~ ")";
    if (stoc & STC.IMMUTABLE) s = "immutable(" ~ s ~ ")";
    if (stoc & STC.SHARED   ) s =    "shared(" ~ s ~ ")";

    // parameter storage class (in this order for "lazy scope T")
    if (stoc & STC.SCOPE) s = "scope " ~ s;
    if (stoc & STC.IN   ) s =    "in " ~ s;
    if (stoc & STC.OUT  ) s =   "out " ~ s;
    if (stoc & STC.REF  ) s =   "ref " ~ s;
    if (stoc & STC.LAZY ) s =  "lazy " ~ s;

    return s;
}

unittest
{
    alias StorageClass STC;

    enum stc1 = STC.SHARED | STC.CONST;
    static assert(toString(stc1, "T") == "shared(const(T))");

    enum stc2 = STC.SCOPE | STC.LAZY;
    static assert(toString(stc2, "T") == "lazy scope T");
}


/***************************************
A $(D Linkage) member value represents a linkage type used in the
$(D extern) attribute.
 */
enum Linkage
{
    /**
     * Linkage types defined in the _D specification.
     */
    D,
    C,       /// ditto
    WINDOWS, /// ditto
    PASCAL,  /// ditto
    CPP,     /// ditto
}

/// Ditto
string toString(Linkage link) pure nothrow
{
    string s;

    switch (link)
    {
        case Linkage.      D: s =       "D"; break;
        case Linkage.      C: s =       "C"; break;
        case Linkage.WINDOWS: s = "Windows"; break;
        case Linkage. PASCAL: s =  "Pascal"; break;
        case Linkage.    CPP: s =     "C++"; break;

        default: assert(0);
    }
    return s;
}


/***************************************
A bitwise-OR of $(D FunctionAttribute) member values represents function
attributes such as $(D pure nothrow).

Example:
--------------------
alias FunctionAttribute Attr;

Attr atts = Attr.PURE | Attr.NOTHROW;
assert(toString(atts) == "pure nothrow");
--------------------
 */
enum FunctionAttribute : uint
{
    /**
     * No attribute. Note that the value of $(D NONE) is zero; it's
     * actually not a bit mask. See also the description of
     * the $(D $(LINK2 #StorageClass, StorageClass)._NONE).
     */
    NONE = 0,

    /**
     * General function attributes.
     */
    PURE    = 1 << 0,
    NOTHROW = 1 << 1, /// ditto
    REF     = 1 << 2, /// ditto
}

/// Ditto
string toString(FunctionAttribute atts) pure nothrow
{
    alias FunctionAttribute FA;
    string s = "";

    if (atts & FA.PURE   ) s ~=    "pure ";
    if (atts & FA.NOTHROW) s ~= "nothrow ";
    if (atts & FA.REF    ) s ~=     "ref ";

    return s.length ? s[0 .. $ - 1] : s;
}

unittest
{
    alias FunctionAttribute FA;

    enum fa1 = FA.PURE | FA.NOTHROW;
    static assert(toString(fa1) == "pure nothrow");
}


/***************************************
A $(D Variadic) member value indicates the "variadicity" of a function.

Example:

Use $(D toString) to generate function parameter declarations.
--------------------
alias Variadic V;

string params = "real a, int[] b";
assert(toString(V.NO, params) == "real a, int[] b");
assert(toString(V.VARIADIC, params) == "real a, int[] b, ...");
assert(toString(V.TYPESAFE, params) == "real a, int[] b...");
--------------------
 */
enum Variadic
{
    NO,       /// Not variadic.
    VARIADIC, /// Classic variadic function ( a, b, ... ).
    TYPESAFE, /// Typesafe variadic function ( a, b[] ...).
}

/// Ditto
string toString(Variadic var, string params) pure nothrow
{
    string s = params;

    if (var == Variadic.TYPESAFE)
    {
        s ~= "...";
    }
    else if (var == Variadic.VARIADIC)
    {
        s ~= s.length ? ", ..." : "...";
    }
    return s;
}

unittest
{
    static assert(toString(Variadic.NO, "int, byte") == "int, byte");
    static assert(toString(Variadic.VARIADIC, "int, byte") ==
            "int, byte, ...");
    static assert(toString(Variadic.TYPESAFE, "int, byte[]") ==
            "int, byte[]...");
}


//===================================================================//
// CTFE-friendly compile-time reflected information
//===================================================================//

// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Type information
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
A $(D Type) object represents a type available in D.

There are various kinds of types in D: basic types (such as $(D int)),
array types, user-defined types, etc. The $(D kind) field indicates
which kind of type is represented by a $(D Type) object, and other
fields hold more detailed information. For example, the $(D storage)
field is the storage class applied to the type, and the $(D next) field
is an array of other types referenced by the type.

Example:

Construct a $(D Type) object for $(D immutable(char)[42]). This example
is executable at compile time.
--------------------
// immutable(char)
Type chr;
chr.kind = Type.Kind.CHAR;
chr.storage = StorageClass.IMMUTABLE;

// chr[42]
Type str;
str.kind = Type.Kind.SARRAY;
str.next = [ chr ];
str.length = 42;

assert(toString(str) == "immutable(char)[42]");
--------------------
 */
struct Type
{
    /**
     * The $(D kind) field indicates which _kind of type is
     * represented by this object. The value can be one of these:
     */
    enum Kind
    {
        /**
         * No type. No other fields are used.
         */
        NONE,

        /**
         * Basic types.
         */
        VOID,
        BYTE,    /// ditto
        UBYTE,   /// ditto
        SHORT,   /// ditto
        USHORT,  /// ditto
        INT,     /// ditto
        UINT,    /// ditto
        LONG,    /// ditto
        ULONG,   /// ditto
        CENT,    /// ditto
        UCENT,   /// ditto
        FLOAT,   /// ditto
        DOUBLE,  /// ditto
        REAL,    /// ditto
        IFLOAT,  /// ditto
        IDOUBLE, /// ditto
        IREAL,   /// ditto
        CFLOAT,  /// ditto
        CDOUBLE, /// ditto
        CREAL,   /// ditto
        BOOL,    /// ditto
        CHAR,    /// ditto
        WCHAR,   /// ditto
        DCHAR,   /// ditto

        /**
         * Dynamic and static array types. The first element of the
         * $(D next) field, $(D next[0]), is the element type and the
         * $(D length) field is the length of the static array.
         */
        ARRAY,
        SARRAY, /// ditto

        /**
         * Associative array type. The first element of the $(D next)
         * field, $(D next[0]), is the key type and the second one,
         * $(D next[1]), is the value type.
         */
        AARRAY,

        /**
         * Pointer type. The first element of the $(D next) field,
         * $(D next[0]), is the referenced type.
         */
        POINTER,

        /**
         * Function and delegate types. Note that a function type is
         * not a function pointer type. A function pointer type is a
         * pointer type that references a function type.
         *
         * $(UL
         *  $(LI The first element of the $(D next) field,
         *     $(D next[0]), is the return type.)
         *  $(LI The rest, $(D next[1 .. $]), are the parameter types.)
         *  $(LI The $(D attributes) field is the function attributes.
         *     It's zero or a bitwise-OR of some $(D FunctionAttribute
         *     ) member values.)
         *  $(LI The $(D linkage) field is the calling convention.)
         *  $(LI The $(D variadic) field indicates whether the
         *     function is variadic.)
         *  $(LI The $(D needThis) field is $(D true) if the function
         *     is a member function or a nested function.)
         * )
         */
        FUNCTION,
        DELEGATE, /// ditto

        /**
         * User-defined types. The $(D symbol) field is the declared
         * symbol of the type. The $(D next) field is an array of the
         * base types (if any).
         */
        IDENT,
        CLASS,   /// ditto
        STRUCT,  /// ditto
        ENUM,    /// ditto
        TYPEDEF, /// ditto

        /**
         * Type tuple. The $(D next) field is an array of the types in
         * the tuple. The $(D storage) field is not used.
         */
        TUPLE,
    }
    Kind kind; /// ditto

    /**
     * The _storage class applied to this type. It's zero or a
     * bitwise-OR of some $(D StorageClass) member values. This field
     * is common to all type kinds but $(D NONE) and $(D TUPLE).
     */
    StorageClass storage;

    /**
     * Other types referenced by this type.
     */
    Type[] next;

    /**
     * The dimension of a static array.
     */
    size_t length;

    /**
     * Information about a function or delegate type.
     */
    FunctionAttribute attributes;
    Linkage              linkage; /// ditto
    Variadic            variadic; /// ditto
    bool                needThis; /// ditto

    /**
     * The symbol, if any, of this type.
     */
    Symbol[] symbol;
}


/**
Ditto
 */
bool equal(in Type ta, in Type tb)
{
    alias Type.Kind T;

    /* General checks.
     */
    if (ta.kind != tb.kind)
        return false;

    // none is none
    if (ta.kind == T.NONE)
        return true;

    // storage class must match
    if (ta.storage != tb.storage)
        return false;

    // symbol must match (if any)
    if (ta.symbol.length || tb.symbol.length)
    {
        if (ta.symbol.length != tb.symbol.length)
            return false;

        if (!equal(ta.symbol[0], tb.symbol[0]))
            return false;
    }

    /* Kind-specific checks
     */
    switch (ta.kind)
    {
        case T.FUNCTION, T.DELEGATE:
        {
            // Function modifiers must match.
            if (ta.attributes != tb.attributes ||
                ta.linkage    != tb.linkage    ||
                ta.variadic   != tb.variadic)
            {
                return false;
            }
            break;
        }

        case T.SARRAY:
        {
            // dimensions must match
            if (ta.length != tb.length)
                return false;
            break;
        }

        case T.ARRAY, T.AARRAY, T.POINTER,
             T.CLASS, T.STRUCT, T.ENUM, T.TYPEDEF,
             T.TUPLE:
            break;

        // No more test is needed
        default:
            return true;
    }

    /* Check for the referenced types.
     */
    if (ta.next.length != tb.next.length)
        return false;

    foreach (i; 0 .. ta.next.length)
    {
        if (!equal(ta.next[i], tb.next[i]))
            return false;
    }

    // Congratulations!
    return true;
}

unittest
{
    alias Type.Kind    T;
    alias StorageClass STC;

    enum t1 = Type(T.NONE);
    static assert(equal(t1, t1));

    enum t2a = Type(T.INT);
    enum t2b = Type(T.INT, STC.CONST);
    enum t2c = Type(T.SHORT);
    static assert( equal(t2a, t2a));
    static assert( equal(t2b, t2b));
    static assert( equal(t2c, t2c));
    static assert(!equal(t2a, t2b));
    static assert(!equal(t2b, t2c));
    static assert(!equal(t2c, t2a));

    enum t3a = Type(T.ARRAY, STC.NONE, [ Type(T.INT) ]);
    enum t3b = Type(T.SARRAY, STC.NONE, [ Type(T.INT) ], 4);
    static assert( equal(t3a, t3a));
    static assert( equal(t3b, t3b));
    static assert(!equal(t3a, t3b));
}


/**
Ditto
 */
string toString(Type ty)
{
    alias Type.Kind    T;
    alias StorageClass STC;

    switch (ty.kind)
    {
        case T.NONE:
            return null;

        // String representation of function (delegate) type is
        // different from that of other types.
        case T.FUNCTION, T.DELEGATE:
            return toString_function(ty);

        // So is tuple.
        case T.TUPLE:
            return toString_tuple(ty);

        default:
            return toString(ty.storage, toString_withoutStoc(ty));
    }
}

unittest
{
    alias StorageClass STC;

    enum t1 = Type(Type.Kind.INT, STC.CONST | STC.REF);
    static assert(toString(t1) == "ref const(int)");

    enum t2 = Type(Type.Kind.INT, STC.SCOPE | STC.LAZY | STC.CONST);
    static assert(toString(t2) == "lazy scope const(int)");
}


/*
Converts a type $(D ty) to its string representation ignoring the
storage class. $(D ty) cannot be neither $(D NONE), $(D FUNCTION),
$(D DELEGATE) nor $(D TUPLE).
 */
private string toString_withoutStoc(Type ty)
in
{
    assert(ty.kind != Type.Kind.NONE);
}
body
{
    alias Type.Kind T;

    /* Try basic types.
     */
    static immutable string[T.max + 1] BASIC_TYPE_NAME =
        // XXX: Bugzilla #3026 must be fixed
    [
        T.VOID  :   "void",
        T.BYTE  :   "byte", T.UBYTE  :   "ubyte",
        T.SHORT :  "short", T.USHORT :  "ushort",
        T.INT   :    "int", T.UINT   :    "uint",
        T.LONG  :   "long", T.ULONG  :   "ulong",
        T.CENT  :   "cent", T.UCENT  :   "ucent", // TBD
        T.FLOAT :  "float", T.IFLOAT :  "ifloat", T.CFLOAT :  "cfloat",
        T.DOUBLE: "double", T.IDOUBLE: "idouble", T.CDOUBLE: "cdouble",
        T.REAL  :   "real", T.IREAL  :   "ireal", T.CREAL  :   "creal",
        T.BOOL  :   "bool",
        T.CHAR  :   "char", T.WCHAR  :   "wchar", T.DCHAR  :   "dchar",
    ];
    if (BASIC_TYPE_NAME[ty.kind])
        return BASIC_TYPE_NAME[ty.kind];

    /* More complex types
     */
    switch (ty.kind)
    {
        case T.ARRAY, T.SARRAY: return toString_array(ty);
        case T.AARRAY : return toString_assocArray(ty);
        case T.POINTER: return toString_pointer(ty);

        // User-defined types
        case T.IDENT  : return toString(ty.symbol[0]);
        case T.CLASS  : return   "class " ~ toString(ty.symbol[0]);
        case T.STRUCT : return  "struct " ~ toString(ty.symbol[0]);
        case T.ENUM   : return    "enum " ~ toString(ty.symbol[0]);
        case T.TYPEDEF: return "typedef " ~ toString(ty.symbol[0]);

        default: assert(0); // does not reach
    }
}

unittest
{
    alias    Type.Kind T;
    alias StorageClass STC;
    alias  Symbol.Kind S;

    enum t1 = Type(T.REAL, STC.CONST);
    static assert(toString_withoutStoc(t1) == "real"); // w/o const

    enum t2 = makeStruct!(Type,
              "kind", T.CLASS,
            "symbol", [ Symbol(S.IDENTIFIER, "MyClass") ]);
    static assert(toString_withoutStoc(t2) == "class MyClass");
}


/*
Converts a dynamic/static array type $(D ty) into its string
representation. This function rewrites immutable(char)[] to string;
wstring and dstring as well. The direct storage class is ignored.
 */
private string toString_array(Type ty)
in
{
    assert(ty.kind == Type.Kind.ARRAY ||
           ty.kind == Type.Kind.SARRAY);
    assert(ty.next.length == 1);
}
body
{
    alias    Type.Kind T;
    alias StorageClass STC;

    auto next = ty.next[0];

    if (ty.kind == Type.Kind.SARRAY)
    {
        // static array
        uintmax_t dim = ty.length;
        return toString(next) ~ "[" ~ toString(dim) ~ "]";
    }
    else
    {
        // dynamic array
        enum
        {
            Timmchar = Type(T.CHAR, STC.IMMUTABLE),
            Timmwchar = Type(T.WCHAR, STC.IMMUTABLE),
            Timmdchar = Type(T.DCHAR, STC.IMMUTABLE),
        }

        if (equal(next, Timmchar)) return "string";
        if (equal(next, Timmwchar)) return "wstring";
        if (equal(next, Timmdchar)) return "dstring";

        return toString(next) ~ "[]";
    }
}

unittest
{
    alias    Type.Kind T;
    alias StorageClass STC;

    enum t1 = Type(T.ARRAY, STC.NONE,
            [ Type(T.INT, STC.SHARED) ]);
    static assert(toString(t1) == "shared(int)[]");

    enum t2 = Type(T.SARRAY, STC.NONE,
            [ Type(T.SHORT, STC.CONST) ], 42);
    static assert(toString(t2) == "const(short)[42]");

    // special cases
    enum tcstr = Type(T.ARRAY, STC.CONST,
            [ Type(T.CHAR, STC.IMMUTABLE) ]);
    static assert(toString(tcstr) == "const(string)");

    enum twstr = Type(T.ARRAY, STC.CONST,
            [ Type(T.WCHAR, STC.IMMUTABLE) ]);
    static assert(toString(twstr) == "const(wstring)");

    enum tdstr = Type(T.ARRAY, STC.CONST,
            [ Type(T.DCHAR, STC.IMMUTABLE) ]);
    static assert(toString(tdstr) == "const(dstring)");
}


/*
Converts an associative array type $(D ty) into its string
representation. The direct storage class is ignored.
 */
private string toString_assocArray(Type ty)
in
{
    assert(ty.kind == Type.Kind.AARRAY);
    assert(ty.next.length == 2);
}
body
{
    const kname = toString(ty.next[0]);
    const vname = toString(ty.next[1]);
    return vname ~ "[" ~ kname ~ "]";
}

unittest
{
    alias    Type.Kind T;
    alias StorageClass STC;

    enum t1 = Type(T.AARRAY, STC.CONST,
            [ Type(T.CHAR), Type(T.REAL) ]);
    static assert(toString(t1) == "const(real[char])");
}


/*
Converts a pointer type $(D ty) into its string representation. The
direct storage class is ignored.
 */
private string toString_pointer(Type ty)
in
{
    assert(ty.kind == Type.Kind.POINTER);
}
body
{
    Type next = ty.next[0];

    // function pointer has its own syntax
    if (next.kind == Type.Kind.FUNCTION)
    {
        next.symbol =
            [ Symbol(Symbol.Kind.IDENTIFIER, "function") ];
        return toString(next);
    }

    // usual pointer syntax
    return toString(next) ~ "*";
}

unittest
{
    alias         Type.Kind T;
    alias      StorageClass STC;
    alias FunctionAttribute FA;

    enum t1 = Type(T.POINTER, STC.NONE,
            [ Type(T.CHAR, STC.IMMUTABLE) ]);
    static assert(toString(t1) == "immutable(char)*");

    enum t2f = Type(T.FUNCTION, STC.NONE,
                [ Type(T.VOID) ], 0, FA.NOTHROW);
    enum t2 = Type(T.POINTER, STC.NONE, [ t2f ]);
    static assert(toString(t2) == "nothrow void function()");
}


/*
Converts a function (delegate) type $(D ty) into its string
representation. A calling convention comes first, and storage class,
attributes, return type, name (if any), and parameters follow.

Examples:
--------------------
"pure nothrow real(real)"
"const ref int delegate(out int r, in int[] a...)"
"pure nothrow real std.math.pow(real, real)"
--------------------
 */
private string toString_function(Type ty)
in
{
    assert(ty.kind == Type.Kind.FUNCTION ||
           ty.kind == Type.Kind.DELEGATE);
}
body
{
    alias FunctionAttribute FA;
    alias      StorageClass STC;

    /* Calling convention: extern(C++) or something. The D calling
     * convention should be omitted.
     */
    string xtern = "";

    if (ty.linkage != Linkage.D)
        xtern = "extern(" ~ toString(ty.linkage) ~ ") ";

    /* Storage class and function attributes
     */
    string stoc = "";

    if (ty.storage & STC.SHARED   ) stoc ~=    "shared ";
    if (ty.storage & STC.CONST    ) stoc ~=     "const ";
    if (ty.storage & STC.IMMUTABLE) stoc ~= "immutable ";

    // attributes
    string atts = toString(ty.attributes);

    if (atts.length)
        atts ~= " "; // need a space before the return type

    /* Return type is stored in next[0].
     */
    auto rtype = toString(ty.next[0]);

    /* Function name, "function" or "delegate". Function name (ty.qname)
     * is set when this type is used with symbol name; it's also set
     * to "function" when the type is used via a function pointer.
     *
     * It's empty if the type is JUST a function type. "pure int(int)"
     */
    string fun;

    if (ty.symbol)
        fun = toString(ty.symbol[0]);
    else if (ty.kind == Type.Kind.DELEGATE)
        fun = "delegate";

    if (fun.length)
        fun = " " ~ fun; // need a space after the return type

    /* Parameters: join parameter types (which are in next[1 .. $])
     * with ", ". Parameter storage class is handled by toString(Type).
     */
    string params = "";

    foreach (i, pt; ty.next[1 .. $])
    {
        if (i >= 1)
            params ~= ", ";
        params ~= toString(pt);
    }

    // Deal with variadic arguments.
    params = toString(ty.variadic, params);

    /* Compose.
     */
    return xtern ~ stoc ~ atts ~ rtype ~ fun ~ "(" ~ params ~ ")";
}

unittest
{
    alias         Type.Kind T;
    alias      StorageClass STC;
    alias FunctionAttribute FA;

    enum t1 = Type(T.FUNCTION, STC.CONST,
        [ Type(T.INT), Type(T.UINT, STC.SCOPE) ],
        0,
        FA.REF | FA.NOTHROW, Linkage.C, Variadic.VARIADIC);
    static assert(toString_function(t1) ==
            "extern(C) const nothrow ref int(scope uint, ...)");

    enum t2 = Type(T.FUNCTION, STC.NONE,
        [ Type(T.REAL), Type(T.REAL) ],
        0,
        FA.PURE | FA.NOTHROW, Linkage.D, Variadic.NO, false,
        [ createSymbol([ "std", "math", "sin" ]) ]);
    static assert(toString_function(t2) ==
            "pure nothrow real std.math.sin(real)");

    enum t3 = Type(T.DELEGATE, STC.NONE,
        [ Type(T.VOID), Type(T.ARRAY, STC.IN, [ Type(T.INT) ]) ],
        0,
        FA.NONE, Linkage.D, Variadic.TYPESAFE);
    static assert(toString_function(t3) ==
            "void delegate(in int[]...)");
}


/*
Converts a TypeTuple $(D ty) into its string representation. This
function does not deal with storage class nor nested tuples.
 */
private string toString_tuple(Type ty)
in
{
    assert(ty.kind == Type.Kind.TUPLE);
    assert(ty.storage == 0, "storage class is undefined for tuple");
}
body
{
    string s = "(";

    if (ty.next) // [workaround] CTFE
    foreach (i, t; ty.next)
    {
        if (i >= 1)
            s ~= ", ";
        s ~= toString(t);
    }
    s ~= ")";
    return s;
}

unittest
{
    alias StorageClass STC;

    enum t1 = Type(Type.Kind.TUPLE);
    static assert(toString_tuple(t1) == "()");

    enum t2 = Type(Type.Kind.TUPLE, STC.NONE,
            [ Type(Type.Kind.BYTE) ]);
    static assert(toString_tuple(t2) == "(byte)");

    enum t3 = Type(Type.Kind.TUPLE, STC.NONE,
            [ Type(Type.Kind.INT), Type(Type.Kind.DCHAR) ]);
    static assert(toString_tuple(t3) == "(int, dchar)");
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Literal values
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
A $(D Literal) object represents a compile-time constant value.

A compile-time constant value is $(D null), an integer, a floating
point, a complex floating point, an array, an associative array, a
string or a struct. The $(D kind) field indicates which kind of literal
is stored in a $(D Literal) object.

Example:

Construct a complex floating point literal. Floating point values are
converted to hexadecimal strings.
--------------------
auto val = Literal(Literal.Kind.COMPLEX);
val.re = 3.5;
val.im = 0;
val.suffix = "L";
assert(toString(val) == "0x1.Cp1L + 0x0p0Li");
--------------------
*/
struct Literal
{
    /**
     * The $(D kind) field indicates which kind of literal value is
     * represented by this object. The value can be one of these:
     */
    enum Kind
    {
        /**
         * Null. No other fields are used.
         */
        NULL,

        /**
         * Integer. The $(D integer) field holds the integral value
         * as a unsigned integer. The $(D suffix) field holds the
         * integer suffix ($(D U) and/or $(D L)).
         */
        INTEGER,

        /**
         * Real or imaginary. The $(D re) field holds the floating
         * point value. The $(D suffix) field holds the floating point
         * suffix ($(D F) or $(D L); and/or $(D i)).
         */
        FLOAT,

        /**
         * Complex floating point. The $(D re) field holds the real
         * part and the $(D im) field holds the imaginary part. The
         * $(D suffix) field holds the floating point suffix ($(D F)
         * or $(D L)) that is applied to the both parts.
         */
        COMPLEX,

        /**
         * Array or associative array. The $(D next) field is an array
         * of the elements. For an associative array, keys and values
         * are interleaved as $(D [ key, value, key, value, ... ]).
         */
        ARRAY,

        /**
         * String. The $(D text) field holds the string in UTF-8. The
         * $(D suffix) field holds the string suffix ($(D c), $(D w)
         * or $(D d)).
         */
        STRING,

        /**
         * Struct. The $(D next) field is an array of the field
         * initializers.
         */
        STRUCT,
    }
    Kind kind; /// Ditto

    /**
     * The value of an _integer literal casted to an unsigned _integer
     * type. Whether the actual value is signed or unsigned is
     * detemined by the $(D suffix) field or external type information.
     */
    uintmax_t integer;

    /**
     * The real and imaginary parts of a floating point value.
     */
    real re;
    real im; /// ditto

    /**
     * A string literal in UTF-8.
     */
    string text;

    /**
     * The _suffix appended to this literal.
     */
    string suffix;

    /**
     * Other literals referenced by this literal.
     */
    Literal[] next;
}


/**
Ditto
 */
bool equal(in Literal va, in Literal vb)
{
    alias Literal.Kind V;

    if (va.kind != vb.kind)
        return false;

    switch (va.kind)
    {
        case V.NULL:
            return true; // both are null

        case V.INTEGER:
            return va.integer == vb.integer && va.suffix == vb.suffix;

        case V.FLOAT:
            return equal(va.re, vb.re) && va.suffix == vb.suffix;

        case V.COMPLEX:
            return equal(va.re, vb.re) && equal(va.im, vb.im) &&
                   va.suffix == vb.suffix;

        case V.STRING:
            return va.text == vb.text && va.suffix == vb.suffix;

        // check for all elements
        case V.ARRAY, V.STRUCT:
        {
            if (va.next.length != vb.next.length)
                return false;

            foreach (i; 0 .. va.next.length)
            {
                if (!equal(va.next[i], vb.next[i]))
                    return false;
            }
            return true;
        }

        // does not reach
        default: assert(0);
    }
}

unittest
{
    alias Literal.Kind V;

    enum v1 = Literal(V.NULL);
    static assert(equal(v1, v1));

    enum v2a = Literal(V.INTEGER,  42);
    enum v2b = Literal(V.INTEGER, -42);
    enum v2c = Literal(V.COMPLEX, 0, real.nan, 0);
    static assert( equal(v2a, v2a));
    static assert( equal(v2b, v2b));
    static assert( equal(v2c, v2c));
    static assert(!equal(v2a, v2b));
    static assert(!equal(v2b, v2c));
    static assert(!equal(v2c, v2a));

    enum v3a = makeStruct!(Literal,
            "kind", V.STRING, "text", "abc", "suffix", "c");
    enum v3b = makeStruct!(Literal,
            "kind", V.STRING, "text", "abc", "suffix", "w");
    enum v3c = makeStruct!(Literal,
            "kind", V.STRING, "text", "cba", "suffix",  "");
    static assert( equal(v3a, v3a));
    static assert( equal(v3b, v3b));
    static assert( equal(v3c, v3c));
    static assert(!equal(v3a, v3b));
    static assert(!equal(v3b, v3c));
    static assert(!equal(v3c, v3a));

    enum v4a = makeStruct!(Literal,
            "kind", V. ARRAY, "next", [ Literal(V.INTEGER, 42) ]);
    enum v4b = makeStruct!(Literal,
            "kind", V.STRUCT, "next", [ Literal(V.INTEGER, 42) ]);
    static assert( equal(v4a, v4a));
    static assert( equal(v4b, v4b));
    static assert(!equal(v4a, v4b));
}

/*
[internal] a == b or both are NaN
 */
private bool equal(real a, real b) pure nothrow
{
    return a == b || (a !<>= 0 && b !<>= 0);
}

unittest
{
    static assert( equal(1.L, 1.L));
    static assert(!equal(1.L, 2.L));
    static assert( equal(real.nan, real.nan));
    static assert(!equal(1.L, real.nan));
    static assert( equal(real.infinity, real.infinity));
    static assert(!equal(-real.infinity, real.infinity));
}


/**
Ditto
 */
string toString(Literal val, Type ty = Type.init)
{
    alias Literal.Kind V;
    alias    Type.Kind T;

    // Type is unspecified. Use the deduced one.
    if (ty.kind == T.NONE)
        ty = deduceType(val);

    // hub
    switch (val.kind)
    {
        case V.NULL:
            return toString_nullLiteral(ty);

        case V.INTEGER:
            return toString_integer(val, ty);

        case V.FLOAT:
            return toString_float(val, ty);

        case V.COMPLEX:
            return toString_complex(val, ty);

        case V.ARRAY:
            if (ty.kind == T.ARRAY || ty.kind == T.SARRAY)
                return toString_array(val, ty);
            if (ty.kind == T.AARRAY)
                return toString_assocArray(val, ty);
            assert(0);

        case V.STRUCT:
            return toString_struct(val, ty);

        case V.STRING:
            return toString_string(val, ty);

        default: assert(0); // does not reach
    }
}


/*
Returns a unary expression string representing a $(D null) of the
specified type $(D ty).
 */
private string toString_nullLiteral(Type ty)
{
    enum Tnull = deduceType(Literal(Literal.Kind.NULL));

    if (equal(ty, Tnull))
        return "null";
    else
        return "cast(" ~ toString(ty) ~ ") null";
}

unittest
{
    alias Type.Kind    T;
    alias StorageClass STC;

    enum t1 = Type(T.POINTER, STC.NONE, [ Type(T.VOID) ]);
    static assert(toString_nullLiteral(t1) == "null");

    enum t2 = Type(T.ARRAY, STC.NONE, [ Type(T.CHAR) ]);
    static assert(toString_nullLiteral(t2) == "cast(char[]) null");

    enum t3 = Type(T.POINTER, STC.NONE, [ Type(T.VOID, STC.CONST) ]);
    static assert(toString_nullLiteral(t3) ==
            "cast(const(void)*) null");
}


/*
Returns a unary expression string representing the integer literal
$(D val) of the type $(D ty).

The result will look like: "cast(short) 1234"
 */
private string toString_integer(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.INTEGER);
}
body
{
    alias Type.Kind T;
    string s;
    bool needcast;

    switch (ty.kind)
    {
        default:
            s = toString(cast(intmax_t) val.integer);
            break;

        case T.FLOAT, T.DOUBLE, T.REAL:
        case T.UBYTE, T.USHORT, T.UINT, T.ULONG, T.UCENT:
            s = toString(cast(uintmax_t) val.integer);
            break;
    }

    // Integer literal doesn't have storage class.
    if (ty.storage != StorageClass.NONE)
    {
        needcast = true;
    }
    else
    {
        // Try to reduce the cast by appending a suffix.
        switch (ty.kind)
        {
            case T.  INT:            break;
            case T. UINT: s ~= "U" ; break;
            case T. LONG: s ~=  "L"; break;
            case T.ULONG: s ~= "UL"; break;

            // Need explicit convertion.
            default:
                needcast = true;
                break;
        }
    }

    // Finish.
    if (needcast)
        s = "cast(" ~ toString(ty) ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;

    enum v = Literal(V.INTEGER, 42);
    enum t1 = Type(T.INT);
    enum t2 = Type(T.UINT);
    enum t3 = Type(T.LONG);
    enum t4 = Type(T.ULONG);
    enum t5 = Type(T.USHORT);
    enum t6 = Type(T.REAL);
    static assert(toString_integer(v, t1) == "42");
    static assert(toString_integer(v, t2) == "42U");
    static assert(toString_integer(v, t3) == "42L");
    static assert(toString_integer(v, t4) == "42UL");
    static assert(toString_integer(v, t5) == "cast(ushort) 42");
    static assert(toString_integer(v, t6) == "cast(real) 42");
}


/*
Returns a unary expression string representing the floating point
literal $(D val) of the type $(D ty).

The result will look like: "0x1.2p3L"
 */
private string toString_float(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.FLOAT);
}
body
{
    alias Type.Kind T;
    auto tname = toString(ty);
    string s = toHexString(val.re);

    /* Handle special values.
     */
    switch (s)
    {
        // Assuming ty is a floating point type.
        case       "NaN": return       tname ~ ".nan";
        case  "Infinity": return       tname ~ ".infinity";
        case "-Infinity": return "-" ~ tname ~ ".infinity";
        default: break;
    }

    /* Usual floating point literal. Notice imaginary types.
     */
    bool needcast;

    if (ty.storage != StorageClass.NONE)
    {
        // Floating point literal does not have any storage class.
        needcast = true;
    }
    else
    {
        // Try to reduce the cast by appending a suffix.
        switch (ty.kind)
        {
            case T.FLOAT , T.IFLOAT : s ~= "F"; break;
            case T.DOUBLE, T.IDOUBLE:           break;
            case T.REAL  , T.IREAL  : s ~= "L"; break;

            default:
                needcast = true;
                break;
        }
    }

    /* Deal with imaginary types. Simply append the 'i' suffix.
     */
    switch (ty.kind)
    {
        case T.IFLOAT, T.IDOUBLE, T.IREAL:
            s ~= "i";
            break;

        default: break;
    }

    // Finish.
    if (needcast)
        s = "cast(" ~ tname ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;

    enum v1 = Literal(V.FLOAT, 0, 0x1.2p34);
    enum t11 = Type(T.FLOAT);
    enum t12 = Type(T.DOUBLE);
    enum t13 = Type(T.REAL);
    enum t14 = Type(T.INT);
    static assert(toString_float(v1, t11) == "0x1.2p34F");
    static assert(toString_float(v1, t12) == "0x1.2p34");
    static assert(toString_float(v1, t13) == "0x1.2p34L");
    static assert(toString_float(v1, t14) == "cast(int) 0x1.2p34");

    enum v2 = Literal(V.FLOAT, 0, real.nan);
    enum t21 = Type(T.FLOAT);
    enum t22 = Type(T.DOUBLE);
    enum t23 = Type(T.REAL);
    enum t24 = Type(T.REAL, STC.CONST);
    static assert(toString_float(v2, t21) == "float.nan");
    static assert(toString_float(v2, t22) == "double.nan");
    static assert(toString_float(v2, t23) == "real.nan");
    static assert(toString_float(v2, t24) == "const(real).nan");

    enum v3 = Literal(V.FLOAT, 0, real.infinity);
    enum t31 = Type(T.FLOAT);
    enum t32 = Type(T.DOUBLE);
    enum t33 = Type(T.REAL);
    enum t34 = Type(T.REAL, STC.CONST);
    static assert(toString_float(v3, t31) == "float.infinity");
    static assert(toString_float(v3, t32) == "double.infinity");
    static assert(toString_float(v3, t33) == "real.infinity");
    static assert(toString_float(v3, t34) == "const(real).infinity");

    enum v4 = Literal(V.FLOAT, 0, -real.infinity);
    enum t41 = Type(T.FLOAT);
    enum t42 = Type(T.DOUBLE);
    enum t43 = Type(T.REAL);
    enum t44 = Type(T.REAL, STC.CONST);
    static assert(toString_float(v4, t41) == "-float.infinity");
    static assert(toString_float(v4, t42) == "-double.infinity");
    static assert(toString_float(v4, t43) == "-real.infinity");
    static assert(toString_float(v4, t44) == "-const(real).infinity");
}


/*
Returns a unary expression string representing the complex literal
$(D val) of the type $(D ty).

The result would look like: "0x1.2p3 + 0x4.5p6i"
 */
private string toString_complex(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.COMPLEX);
}
body
{
    alias Literal.Kind V;
    alias    Type.Kind T;

    /* Handle special case. Note that Complex.infinity does not make
     * sense. We only handle NaN + NaNi.
     */
    if (val.re !<>= 0 && val.im !<>= 0)
    {
        // Assuming ty is a complex type.
        return toString(ty) ~ ".nan";
    }

    /* Split into real and imaginary parts.
     */
    auto re = Literal(V.FLOAT, 0, val.re);
    auto im = Literal(V.FLOAT, 0, val.im);

    // Deduce the types of re and im.
    Type rety, imty;

    bool needcast = (ty.storage != 0);

    // real part
    switch (ty.kind)
    {
        case T.CFLOAT : rety.kind = T.FLOAT ; break;
        case T.CDOUBLE: rety.kind = T.DOUBLE; break;
        case T.CREAL  : rety.kind = T.REAL  ; break;

        default:
            // deduced type should be FLOAT, DOUBLE or REAL
            rety     = deduceType(re);
            needcast = true;
            break;
    }

    // imaginary part should have the same precision as the real part
    switch (rety.kind)
    {
        case T.FLOAT : imty.kind = T.IFLOAT ; break;
        case T.DOUBLE: imty.kind = T.IDOUBLE; break;
        case T.REAL  : imty.kind = T.IREAL  ; break;

        default: assert(0); // does not reach
    }

    /* Separately convert re & im to string using the deduced types.
     */
    auto restr = toString_float(re, rety);
    auto imstr = toString_float(im, imty);

    // Compose a complex literal.
    string s = restr;

    if (startsWith(imstr, "-"))
        s ~= " - " ~ imstr[1 .. $];
    else
        s ~= " + " ~ imstr;

    // Finish.
    if (needcast)
        s = "cast(" ~ toString(ty) ~ ") (" ~ s ~ ")";
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;

    enum v1 = Literal(V.COMPLEX, 0, 0x1.2p3, -0x1.45p6);
    enum t11 = Type(T.CFLOAT);
    enum t12 = Type(T.CDOUBLE);
    enum t13 = Type(T.CREAL);
    enum t14 = Type(T.CREAL, STC.CONST);
    static assert(toString_complex(v1, t11) == "0x1.2p3F - 0x1.45p6Fi");
    static assert(toString_complex(v1, t12) == "0x1.2p3 - 0x1.45p6i");
    static assert(toString_complex(v1, t13) == "0x1.2p3L - 0x1.45p6Li");
    static assert(toString_complex(v1, t14) ==
            "cast(const(creal)) (0x1.2p3L - 0x1.45p6Li)");

    enum v2 = Literal(V.COMPLEX, 0, real.nan, real.nan);
    enum t2 = Type(T.CREAL, STC.CONST);
    static assert(toString_complex(v2, t2) == "const(creal).nan");

    enum v3 = Literal(V.COMPLEX, 0, real.infinity, 0);
    enum t3 = Type(T.CDOUBLE);
    static assert(toString_complex(v3, t3) ==
            "double.infinity + 0x0p0i");

    enum v4 = Literal(V.COMPLEX, 0, 0, -real.infinity);
    enum t4 = Type(T.CDOUBLE);
    static assert(toString_complex(v4, t4) ==
            "0x0p0 - idouble.infinity");

}


/*
Returns a unary expression string representing the array literal
$(D val) of the type $(D ty).

The result will look like: "[ 1, 2, 3 ]"
 */
private string toString_array(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.ARRAY);
}
body
{
    alias Type.Kind T;

    /* Build the default-typed array literal [ a, b, c ].
     */
    string s = "";

    // Join all elements by ", "
    if (val.next) // [workaround] CTFE
    foreach (i, e; val.next)
    {
        if (i >= 1)
            s ~= ", ";
        s ~= toString(e);
    }

    // enclosing brackets
    if (s.length)
        s = "[ " ~ s ~ " ]";
    else
        s = "[]";

    /* The array literal is a static array. cast?
     */
    bool needcast;

    auto dedty = deduceType(val);
    assert(dedty.kind == T.SARRAY);

    if (equal(ty, dedty) != false)
    {
        // exact match
    }
    else if (ty.kind == T.ARRAY)
    {
        if (ty.storage == dedty.storage &&
            equal(ty.next[0], dedty.next[0]))
        {
            // The given type is just the dynamic version of the
            // deduced type. Just slicing gives the correct type.
            s ~= "[]";
        }
        else
        {
            needcast = true;
        }
    }
    else
    {
        needcast = true;
    }

    // Finish.
    if (needcast)
        s = "cast(" ~ toString(ty) ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;

    enum v1 = Literal(V.ARRAY);
    static assert(toString_array(v1, deduceType(v1)) == "[]");

    enum v2 = makeStruct!(Literal,
            "kind", V.ARRAY,
            "next", [ Literal(V.INTEGER, 1),
                      Literal(V.INTEGER, 2) ]);
    enum t2 = Type(T.ARRAY, STC.NONE, [ Type(T.INT) ]);
    static assert(toString_array(v2, t2) == "[ 1, 2 ][]");

    enum v3 = makeStruct!(Literal,
            "kind", V.ARRAY,
            "next", [ Literal(V.INTEGER, 1),
                      Literal(V.INTEGER, 2) ]);
    enum t3 = Type(T.SARRAY, STC.NONE, [ Type(T.SHORT) ], 2);
    static assert(toString_array(v3, t3) == "cast(short[2]) [ 1, 2 ]");
}


/*
Returns a unary expression string representing the associative array
literal $(D val) of the type $(D ty).

The result will look like: "[ 1: "a", 2: "b" ]"
 */
private string toString_assocArray(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.ARRAY);
    assert(val.next.length % 2 == 0);
}
body
{
    /* Keys and values are interleaved: [ key, val, key, val, ... ]
     */
    string s = "";

    for (size_t i = 0; i < val.next.length; )
    {
        if (i > 0)
            s ~= ", ";

        const skey = toString(val.next[i++]);
        const sval = toString(val.next[i++]);
        s ~= skey ~ ": " ~ sval;
    }

    // enclosing brackets
    if (s.length)
        s = "[ " ~ s ~ " ]";
    else
        s = "[]";

    /* Need cast?
     */
    bool needcast;

    if (val.next.length == 0)
    {
        // Empty [] is void[0]; explicit convertion is necessary
        needcast = true;
    }
    else if (ty.storage != StorageClass.NONE)
    {
        needcast = true;
    }
    else
    {
        // Need cast if ty is different from the deduced type
        assert(val.next.length >= 2);
        needcast = !equal(ty, deduceType(val, Type.Kind.AARRAY));
    }

    // Finish.
    if (needcast)
        s = "cast(" ~ toString(ty) ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;

    enum v1 = Literal(V.ARRAY);
    enum t1 = Type(T.AARRAY, STC.NONE, [ Type(T.INT), Type(T.REAL) ]);
    static assert(toString_assocArray(v1, t1) == "cast(real[int]) []");

    enum v2 = makeStruct!(Literal,
            "kind", V.ARRAY,
            "next",
        [ Literal(V.INTEGER, 1), Literal(V.INTEGER,  10),
          Literal(V.INTEGER, 2), Literal(V.INTEGER, 100) ]);
    enum t2 = Type(T.AARRAY, STC.NONE, [ Type(T.INT), Type(T.INT) ]);
    static assert(toString_assocArray(v2, t2) == "[ 1: 10, 2: 100 ]");
}


/*
Returns a unary expression string representing the struct literal
$(D val) of the type $(D ty).

The result will look like: "mod.S(42, "abc", var)"
 */
private string toString_struct(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.STRUCT);
}
body
{
    /* Build (a, b, c)
     */
    string s = "";

    // Join all elements by ", "

    if (val.next) // [workaround] CTFE
    foreach (i, e; val.next)
    {
        if (i >= 1)
            s ~= ", ";
        s ~= toString(e);
    }

    // enclosing parens
    if (s.length)
        s = "(" ~ s ~ ")";
    else
        s = "()";

    // Prefix the struct name.
    s = toString(ty.symbol[0]) ~ s;

    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias  Symbol.Kind S;

    enum v1 = makeStruct!(Literal,
            "kind", V.STRUCT,
            "next", [ Literal(V.INTEGER, 42),
                      Literal(V.STRING, 0, 0, 0, "abc") ]);
    enum t1 = makeStruct!(Type,
              "kind", T.STRUCT,
            "symbol", [ Symbol(S.IDENTIFIER, "S") ]);
    static assert(toString_struct(v1, t1) == `S(42, "abc")`);
}


/*
Returns a unary expression string representing the string literal
$(D val) of the type $(D ty).
 */
private string toString_string(Literal val, Type ty)
in
{
    assert(val.kind == Literal.Kind.STRING);
}
body
{
    alias Type.Kind    T;
    alias StorageClass STC;

    // common string types
    enum
    {
        STCimm = STC.IMMUTABLE,

        Tstring  = Type(T.ARRAY, STC.NONE, [ Type(T. CHAR, STCimm) ]),
        Twstring = Type(T.ARRAY, STC.NONE, [ Type(T.WCHAR, STCimm) ]),
        Tdstring = Type(T.ARRAY, STC.NONE, [ Type(T.DCHAR, STCimm) ]),
    }

    /* Build the string literal.
     */
    string s = `"` ~ escapeDString(val.text) ~ `"`;

    // Try to eliminate cast by changing the suffix.
    if (val.suffix != "c" && equal(ty,  Tstring)) val.suffix = "c";
    if (val.suffix != "w" && equal(ty, Twstring)) val.suffix = "w";
    if (val.suffix != "d" && equal(ty, Tdstring)) val.suffix = "d";

    // Since string is UTF-8 by default, the suffix 'c' is unnecessary.
    if (val.suffix != "c")
        s ~= val.suffix;

    // Finish.
    if (!equal(ty, deduceType(val)))
        s = "cast(" ~ toString(ty) ~ ") " ~ s;
    return s;
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;
    alias StorageClass STC;

    enum v1 = makeStruct!(Literal,
            "kind", V.STRING,
            "text", "");
    enum t1 = Type(T.ARRAY, STC.NONE,
            [ Type(T.DCHAR, STC.IMMUTABLE) ]);
    static assert(toString_string(v1, t1) == `""d`);

    enum v2 = makeStruct!(Literal,
              "kind", V.STRING,
              "text", `abc\ "def" /ghi`,
            "suffix", "w");
    enum t2 = deduceType(v2);
    static assert(toString_string(v2, t2) == `"abc\\ \"def\" /ghi"w`);
}


/*
Makes the string $(D str) safely quotable.
 */
private string escapeDString(string str) pure nothrow
{
    string es;

    foreach (i, c; str)
    {
        string r;

        switch (c)
        {
            default: break;

            // these characters must be escaped
            case '\"': r = `\"`; break;
            case '\'': r = `\'`; break;
            case '\\': r = `\\`; break; //`//[workaround] vim syn

            // newlines should be escaped
            case '\r': r = `\r`; break;
            case '\n': r = `\n`; break;

            // EOF should be escaped
            case '\x00': r = `\x00`; break;
            case '\x1A': r = `\x1A`; break;
        }

        // copy on write
        if (es)
        {
            if (r)
                es ~= r;
            else
                es ~= c;
        }
        else
        {
            if (r)
                es = str[0 .. i] ~ r;
        }
    }
    return es ? es : str;
}

unittest
{
    static assert(escapeDString("abcd") == "abcd");
    static assert(escapeDString("\r\n") == `\r\n`);
    static assert(escapeDString(`\"`)   == `\\\"`);
    static assert(escapeDString("\x00") == `\x00`);
    static assert(escapeDString("\x1A") == `\x1A`);
}


/*
Returns the default type of the literal value $(D val). Use $(D hint)
to tell the difference b/w array and associative array types.
 */
private Type deduceType(Literal val, Type.Kind hint = Type.Kind.NONE)
{
    alias    Type.Kind T;
    alias Literal.Kind V;
    alias StorageClass STC;

    enum PVOID = Type(T.POINTER, STC.NONE, [ Type(T.VOID) ]);

    // hub
    switch (val.kind)
    {
        case V.NULL   : return PVOID;
        case V.INTEGER: return deduceIntegerType(val);
        case V.FLOAT  : return deduceFloatType(val);
        case V.COMPLEX: return deduceComplexType(val);
        case V.STRING : return deduceStringType(val);
        case V.ARRAY  : return deduceArrayType(val, hint);
        case V.STRUCT : return deduceStructType(val);

        default: assert(0); // does not reach
    }
}

unittest
{
    alias Literal.Kind V;
    alias    Type.Kind T;

    enum v1 = Literal(V.NULL);
    static assert(toString(deduceType(v1)) == "void*");

    enum v2 = Literal(V.INTEGER);
    static assert(toString(deduceType(v2)) == "int");

    enum v3 = Literal(V.FLOAT);
    static assert(toString(deduceType(v3)) == "double");

    enum v4 = Literal(V.COMPLEX);
    static assert(toString(deduceType(v4)) == "cdouble");

    enum v51 = makeStruct!(Literal, "kind", V.STRING, "suffix", "");
    enum v52 = makeStruct!(Literal, "kind", V.STRING, "suffix", "c");
    enum v53 = makeStruct!(Literal, "kind", V.STRING, "suffix", "w");
    enum v54 = makeStruct!(Literal, "kind", V.STRING, "suffix", "d");
    static assert(toString(deduceType(v51)) == "string");
    static assert(toString(deduceType(v52)) == "string");
    static assert(toString(deduceType(v53)) == "wstring");
    static assert(toString(deduceType(v54)) == "dstring");

    enum v61 = Literal(V.ARRAY);
    enum v62 = makeStruct!(Literal,
            "kind", V.ARRAY,
            "next", [ Literal(V.FLOAT), Literal(V.INTEGER) ]);
    static assert(toString(deduceType(v61)) == "void[0]");
    static assert(toString(deduceType(v62)) == "double[2]");

    enum v7 = makeStruct!(Literal,
            "kind", V.ARRAY,
            "next", [ Literal(V.INTEGER), Literal(V.FLOAT) ]);
    static assert(toString(deduceType(v7, T.AARRAY)) == "double[int]");
}

// Notice the suffix U and/or L.
private Type deduceIntegerType(Literal val)
{
    alias Type.Kind T;
    T ty = T.INT;

    switch (val.suffix)
    {
        case "U" : ty = T.UINT ; break;
        case  "L": ty = T. LONG; break;
        case "UL": ty = T.ULONG; break;
        default: break;
    }
    return Type(ty);
}

// Notice the suffix F or L with i.
private Type deduceFloatType(Literal val)
{
    alias Type.Kind T;
    T ty = T.DOUBLE;

    switch (val.suffix)
    {
        case "F" : ty = T. FLOAT ; break;
        case "L" : ty = T. REAL  ; break;
        case "i" : ty = T.IDOUBLE; break;
        case "Fi": ty = T.IFLOAT ; break;
        case "Li": ty = T.IREAL  ; break;
        default: break;
    }
    return Type(ty);
}

// Notice the suffix F or L.
private Type deduceComplexType(Literal val)
{
    alias Type.Kind T;
    T ty = T.CDOUBLE;

    switch (val.suffix)
    {
        case "F": ty = T.CFLOAT; break;
        case "L": ty = T.CREAL ; break;
        default: break;
    }
    return Type(ty);
}

// Deduce from the suffix (default is char).
private Type deduceStringType(Literal val)
{
    alias    Type.Kind T;
    alias StorageClass STC;
    T ety = T.CHAR;

    switch (val.suffix)
    {
        case "c": ety = T. CHAR; break;
        case "w": ety = T.WCHAR; break;
        case "d": ety = T.DCHAR; break;
        default : break;
    }
    return Type(T.ARRAY, STC.NONE, [ Type(ety, STC.IMMUTABLE) ]);
}

// Array literal may be really an associative array literal.
private Type deduceArrayType(Literal val, Type.Kind hint)
{
    alias    Type.Kind T;
    alias StorageClass STC;

    if (val.next.length >= 2 && hint == T.AARRAY)
    {
        // Use the first two elements.
        auto kty = deduceType(val.next[0]);
        auto vty = deduceType(val.next[1]);
        return Type(T.AARRAY, STC.NONE, [ kty, vty ]);
    }
    else
    {
        // Deduce the element type from the first element.
        auto ety = Type(T.VOID);

        if (val.next.length)
            ety = deduceType(val.next[0]);

        return Type(T.SARRAY, STC.NONE, [ ety ], val.next.length);
    }
}

// No way to tell the actual type. Return a dummy type.
private Type deduceStructType(Literal val)
{
    auto ty = Type(Type.Kind.STRUCT);
    ty.symbol = [ Symbol(Symbol.Kind.IDENTIFIER, "struct") ];
    return ty;
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Symbol name
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
A $(D Symbol) object represents a symbol, i.e. an identifier or a
template instance, in D. The $(D kind) field indicates which is
represented by the object.

An identifier is (an alias to) a variable, a function, a template, a
template mixin, a package or a module. An identifier has its name, a
possible parent scope and a possible type. The parent scope is another
symbol. The type is available for variables and functions.

A template instance has its name (the name of the instantiated template
itself), a possible parent scope, and template instantiation arguments.
The name and the parent scope are the same as for identifiers.

Example:

In this example $(D std), $(D std.math), $(D sin), $(D var), $(D Temp)
and $(D Mix) are all identifiers; and $(D Inst) is a template instance.
The parent scope of $(D sin) ($(D std.math.sin)) is the module
$(D std.math), and the grandparent scope is the package $(D std).
$(D std) does not have parent scope.
--------------------
import std.math : sin;
int var;
template Temp(int n) {}
mixin Temp!(42) Mix;
alias Temp!(42) Inst;
--------------------
 */
struct Symbol
{
    /**
     * The $(D kind) field indicates the _kind of the symbol. The value
     * can be one of these:
     */
    enum Kind
    {
        /**
         * Identifier. The first element of the $(D type) field is the
         * type (if any) of the symbol.
         */
        IDENTIFIER,

        /**
         * Template instance. The $(D args) field is an array of the
         * template instantiation arguments.
         */
        TEMPLATE,
    }
    Kind kind; /// ditto

    /**
     * The _name of the symbol itself.
     */
    string name;

    /**
     * If the symbol has a _parent scope, the first element of this
     * field, $(D parent[0]), is a $(D Symbol) object for the _parent
     * scope.
     */
    Symbol[] parent;

    /**
     * See the description of the $(D kind).
     */
    TemplateArgument[] args;
    Type[]             type; /// ditto
}


/*
[internal] For convenience.
 */
version (unittest)
private Symbol createSymbol(string[] hier)
{
    Symbol sym;

    foreach (i, id; hier)
    {
        auto si = Symbol(Symbol.Kind.IDENTIFIER, id);

        if (i == 0)
        {
            sym = si;
        }
        else
        {
            si.parent = [ sym ];
            sym = si;
        }
    }
    return sym;
}

unittest
{
    enum sym1 = createSymbol([ "abc" ]);
    static assert(toString(sym1) == "abc");

    enum sym2 = createSymbol([ "abc", "def" ]);
    static assert(toString(sym2) == "abc.def");
}


/**
Ditto
 */
bool equal(in Symbol sa, in Symbol sb)
{
    if (sa.kind != sb.kind)
        return false;

    if (sa.name != sb.name)
        return false;

    /* Compare template instantiation arguments.
     */
    if (sa.kind == Symbol.Kind.TEMPLATE)
    {
        if (sa.args.length != sb.args.length)
            return false;

        foreach (i; 0 .. sa.args.length)
        {
            if (!equal(sa.args[i], sb.args[i]))
                return false;
        }
    }

    /* Compare types. The type is stored in type[0] (for CTFE).
     * type.length == 0 means a symbol is not typed.
     */
    if (sa.type.length || sb.type.length)
    {
        if (sa.type.length != sb.type.length)
            return false; // either one is untyped

        if (!equal(sa.type[0], sb.type[0]))
            return false;
    }

    /* Check ancestors recursively. Doing this last would reduce the
     * depth of the recursion.
     */
    if (sa.parent.length || sb.parent.length)
    {
        if (sa.parent.length != sb.parent.length)
            return false;

        if (!equal(sa.parent[0], sb.parent[0]))
            return false;
    }

    return true;
}

unittest
{
    alias Symbol.Kind S;

    enum s1a = createSymbol([ "x", "y", "a" ]);
    enum s1b = createSymbol([ "z", "y", "a" ]);
    enum s1c = Symbol(S.TEMPLATE, "temp");
    static assert( equal(s1a, s1a));
    static assert( equal(s1b, s1b));
    static assert( equal(s1c, s1c));
    static assert(!equal(s1a, s1b));
    static assert(!equal(s1b, s1c));
    static assert(!equal(s1c, s1a));
}


/**
Ditto
 */
string toString(Symbol sn)
{
    alias   Type.Kind T;
    alias Symbol.Kind S;

    /* The function symbol has a different syntax. Leave it to the
     * toString_function().
     */
    if (sn.type.length && sn.type[0].kind == T.FUNCTION)
    {
        auto ty = sn.type[0];
        sn.type = null; // to prevent infinite recursion
        ty.symbol = [ sn ];

        return toString_function(ty);
    }

    /* Build "Type fully.qualified.name!(args)"
     */
    string s = sn.name;

    // Qualify the name
    if (sn.parent.length)
        s = toString(sn.parent[0]) ~ "." ~ s;

    // Append instantiation arguments.
    if (sn.kind == S.TEMPLATE)
    {
        s ~= "!(";
        if (sn.args) // [workaround] CTFE
        foreach (i, a; sn.args)
        {
            if (i >= 1)
                s ~= ", ";
            s ~= toString(a);
        }
        s ~= ")";
    }

    // Append the type
    if (sn.type.length && sn.type[0].kind != T.NONE)
        s = toString(sn.type[0]) ~ " " ~ s;

    return s;
}

unittest
{
    alias Symbol.Kind S;
    alias   Type.Kind T;

    enum s1 = Symbol(S.IDENTIFIER, "std");
    static assert(toString(s1) == "std");

    enum s2 = Symbol(S.TEMPLATE, "temp", []);
    static assert(toString(s2) == "temp!()");

    enum s3 = makeStruct!(Symbol,
              "kind", S.IDENTIFIER,
              "name", "math",
            "parent", [ s1 ]);
    static assert(toString(s3) == "std.math");

    enum s4 = makeStruct!(Symbol,
              "kind", S.IDENTIFIER,
              "name", "PI",
              "type", [ Type(T.REAL) ],
            "parent", [ s3 ]);
    static assert(toString(s4) == "real std.math.PI");

    enum s5 = makeStruct!(Symbol,
              "kind", S.IDENTIFIER,
              "name", "foo",
              "type", [ makeStruct!(Type,
                      "kind", T.FUNCTION,
                      "next", [ Type(T.VOID) ]) ],
            "parent", [ s2 ]);
    static assert(toString(s5) == "void temp!().foo()");
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Template argument
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
A $(D TemplateArgument) object represents a template instantiation
argument.

A template instantiation argument is a type, a literal value, or a
symbol. The $(D kind) field indicates which kind of template argument
is stored in a $(D TemplateArgument) object. The $(D type) field is for
a type argument. The $(D type) and $(D value) fields are for a literal
value. The $(D symbol) field is for a symbol argument.

Example:

Examine the result of $(D nonstd.demangle.decodeName).
--------------------
template Temp(T...) {}
alias Temp!(42u) Inst;

Symbol sym = nonstd.demangle.decodeName(Inst.mangleof);

// The first argument is a value 42 of type uint.
TemplateArgument targ = sym.args[0];
assert(targ.kind == TemplateArgument.Kind.VALUE);
assert(targ.value.integer == 42);
assert(toString(targ.type) == "uint");
--------------------
 */
struct TemplateArgument
{
    /**
     * The $(D kind) field indicates which _kind of argument is stored
     * in this object. The value can be one of these:
     */
    enum Kind
    {
        /**
         * Template type argument. The $(D type) field is the type.
         */
        TYPE,

        /**
         * Template value argument (constant value). The $(D value)
         * field is the value and the $(D type) field is the type of
         * the value.
         */
        VALUE,

        /**
         * Template symbol argument (function, template etc.). The
         * $(D symbol) field is the symbol.
         */
        SYMBOL,
    }
    Kind kind; /// ditto

    /**
     * See the description of the $(D kind).
     */
    Type     type;
    Literal value; /// ditto
    Symbol symbol; /// ditto
}


/**
Ditto
 */
bool equal(in TemplateArgument ta, in TemplateArgument tb)
{
    alias TemplateArgument.Kind A;

    if (ta.kind != tb.kind)
        return false;

    switch (ta.kind)
    {
        case A.TYPE  : return equal(ta.type, tb.type);
        case A.VALUE : return equal(ta.type, tb.type) &&
                              equal(ta.value, tb.value);
        case A.SYMBOL: return equal(ta.symbol, tb.symbol);

        default: assert(0);
    }
}

unittest
{
    alias TemplateArgument.Kind A;
    alias             Type.Kind T;
    alias          Literal.Kind V;
    alias           Symbol.Kind S;

    enum a1a = TemplateArgument(A.TYPE, Type(T.INT));
    enum a1b = TemplateArgument(A.TYPE, Type(T.REAL));
    static assert( equal(a1a, a1a));
    static assert( equal(a1b, a1b));
    static assert(!equal(a1a, a1b));

    enum a2a = TemplateArgument(
            A.VALUE, Type(T.INT), Literal(V.INTEGER, 1));
    enum a2b = TemplateArgument(
            A.VALUE, Type(T.INT), Literal(V.INTEGER, 2));
    static assert( equal(a2a, a2a));
    static assert( equal(a2b, a2b));
    static assert(!equal(a2a, a2b));

    static assert(!equal(a1a, a2a));
}


/**
Ditto
 */
string toString(TemplateArgument ta)
{
    alias TemplateArgument.Kind A;

    switch (ta.kind)
    {
        case A.TYPE  : return toString(ta.type);
        case A.VALUE : return toString(ta.value, ta.type);
        case A.SYMBOL: return toString(ta.symbol);
        default: assert(0);
    }
}

unittest
{
}


